#include "binary_search_tree.h"
#include <iostream>

using namespace binarysearchtree;

BinarySearchNode::BinarySearchNode()
{
    this->m_data = 0;
    this->m_parent = NULL;
    this->m_left = NULL;
    this->m_right = NULL;
}

void BinarySearchNode::SetData(int d)
{
    this->m_data = d;
}

void BinarySearchNode::SetParent(BinarySearchNode* p)
{
    this->m_parent = p;
}

void BinarySearchNode::SetLeft(BinarySearchNode* l)
{
    this->m_left = l;
}

void BinarySearchNode::SetRight(BinarySearchNode* r)
{
    this->m_right = r;
}

int BinarySearchNode::GetData()
{
    return this->m_data;
}

BinarySearchNode* BinarySearchNode::GetParent()
{
    return this->m_parent;
}

BinarySearchNode* BinarySearchNode::GetLeft()
{
    return this->m_left;
}

BinarySearchNode* BinarySearchNode::GetRight()
{
    return this->m_right;
}
///////////////////////////////////////////////////
BinarySearchTree::BinarySearchTree(int cap)
{
    this->m_root = NULL;
    this->m_content = new BinarySearchNode[cap];
    this->m_size = 0;
    this->m_cap = cap;
}

BinarySearchTree::~BinarySearchTree()
{
   if(this->m_content != NULL)
      delete this->m_content;
}

void BinarySearchTree::InsertData(int d)
{
    if (this->m_size >= this->m_cap)
        return;

    if (this->m_size == 0)
    {
        this->m_root = &this->m_content[0];
        this->m_root->SetData(d);
        ++this->m_size;
        return;
    }

    BinarySearchNode* pos = this->m_root;
    while (true)
    {
         if (d < pos->GetData())
         {
             if(pos->GetLeft() == NULL)
             {
                  this->m_content[this->m_size].SetData(d);
                  this->m_content[this->m_size].SetParent(pos);
                  pos->SetLeft(&this->m_content[this->m_size]);
                  ++this->m_size;
                  return;
             }
             else
             {
                  pos = pos->GetLeft();
             }
         }
         else
         {
             if (pos->GetRight() == NULL)
             {
                 this->m_content[this->m_size].SetData(d);
                 this->m_content[this->m_size].SetParent(pos);
                 pos->SetRight(&this->m_content[this->m_size]);
                 ++this->m_size;
                 return;
             }
             else
             {
                 pos = pos->GetRight();
             }
         }
    }
}

BinarySearchNode* BinarySearchTree::FindData(int d)
{
    BinarySearchNode* pos = this->m_root;
    while(pos != NULL)
    {
        if (d < pos->GetData())
        {
             pos = pos->GetLeft();
        }
        else if (d > pos->GetData())
        {
            pos = pos->GetRight();
        }
        else
        {
            return pos;
        }
    }

    return NULL;
}

int BinarySearchTree::MinValue()
{
    if (this->m_root == NULL)
        return -1;

    BinarySearchNode* pos = this->m_root;
    while(pos->GetLeft() != NULL)
    {
        pos = pos->GetLeft();
    }

    return pos->GetData();
}

int BinarySearchTree::MaxValue()
{
    if (this->m_root == NULL)
        return -1;

    BinarySearchNode* pos = this->m_root;
    while(pos->GetRight() != NULL)
    {
        pos = pos->GetRight();
    }

    return pos->GetData();
}

void BinarySearchTree::DelData(int d)
{
    BinarySearchNode* pos = this->FindData(d);
    if (pos == NULL)
        return;

    if (pos->GetLeft() == NULL)
    {
        this->transplant(pos, pos->GetRight());
    }
    else if (pos->GetRight() == NULL)
    {
        this->transplant(pos, pos->GetLeft());
    }
    else
    {
        BinarySearchNode* y = this->Successor(pos);
        if (y != pos->GetRight())
        {
            this->transplant(y, y->GetRight());
            y->SetRight(pos->GetRight());
            pos->GetRight()->SetParent(y);
        }

        this->transplant(pos, y);
        y->SetLeft(pos->GetLeft());
        pos->GetLeft()->SetParent(y);
    }
}

void BinarySearchTree::Inorder()
{
    this->inorderhelper(this->m_root);
    std::cout << std::endl;
}

void BinarySearchTree::inorderhelper(BinarySearchNode* n)
{
    if (n == NULL)
        return;

    this->inorderhelper(n->GetLeft());

    std::cout << n->GetData() << " ";

    this->inorderhelper(n->GetRight());
}

BinarySearchNode* BinarySearchTree::Min(BinarySearchNode* n)
{
    if (n == NULL)
        return NULL;

    while (n->GetLeft() != NULL)
    {
        n = n->GetLeft();
    }

    return n;
}

BinarySearchNode* BinarySearchTree::Max(BinarySearchNode* n)
{
    if (n == NULL)
        return NULL;

    while (n->GetRight() != NULL)
    {
        n = n->GetRight();
    }

    return n;
}

void BinarySearchTree::transplant(BinarySearchNode* u, BinarySearchNode* v)
{
    if (u->GetParent() == NULL)
    {
        this->m_root = v;
        return;
    }

    if (u->GetParent()->GetLeft() == u)
    {
        u->GetParent()->SetLeft(v);
    }
    else
    {
        u->GetParent()->SetRight(v);
    }

    if(v != NULL)
    {
        v->SetParent(u->GetParent());
    }
}

BinarySearchNode* BinarySearchTree::Successor(BinarySearchNode* n)
{
    if (n == NULL)
        return NULL;

    if (n->GetRight() != NULL)
    {
        return this->Min(n->GetRight());
    }
    else
    {
        BinarySearchNode* y = n->GetParent();
        while((y != NULL) && (y->GetRight() == n))
        {
              n = y;
              y = n->GetParent();
        }

        return y;
    }
}

BinarySearchNode* BinarySearchTree::Predecessor(BinarySearchNode* n)
{
    if (n == NULL)
        return NULL;

    if (n->GetLeft() != NULL)
    {
        return this->Max(n->GetLeft());
    }
    else
    {
        BinarySearchNode* y = n->GetParent();
        while((y != NULL)&&(y->GetLeft() == n))
        {
            n = y;
            y = n->GetParent();
        }

        return y;
    }
}
